null
(Ed.)
We consider the problem of collective exploration of a known n-
node edge-weighted graph by k mobile agents that have limited energy but are
capable of energy transfers. The agents are initially placed at an arbitrary subset
of nodes in the graph, and each agent has an initial, possibly different, amount
of energy. The goal of the exploration problem is for every edge in the graph to
be traversed by at least one agent. The amount of energy used by an agent to
travel distance x is proportional to x. In our model, the agents can share energy
when co-located: when two agents meet, one can transfer part of its energy to
the other.
For an n-node path, we give an O(n+k) time algorithm that either nds an
exploration strategy, or reports that one does not exist. For an n-node tree with
l leaves, we give an O(n+lk^2) algorithm that finds an exploration strategy if one
exists. Finally, for the general graph case, we show that the problem of deciding
if exploration is possible by energy-sharing agents is NP-hard, even for 3-regular
graphs. In addition, we show that it is always possible to find an exploration
strategy if the total energy of the agents is at least twice the total weight of the
edges; moreover, this is asymptotically optimal.
more »
« less
Full Text Available